from tools_algorithm import *


class Solution:
    def maximumRobots(
        self, chargeTimes: List[int], runningCosts: List[int], budget: int
    ) -> int:

        n = len(runningCosts)

        psm = list(accumulate(runningCosts, initial=0))

        def f(k):
            q = []
            ans = inf
            for i, v in enumerate(chargeTimes):
                while q and v >= q[-1][0]:
                    q.pop()
                q.append((v, i))
                while q and q[0][1] < i - k + 1:
                    q.pop(0)
                if i >= k - 1:
                    ans = min(ans, q[0][0] + k * (psm[i + 1] - psm[i - k + 1]))
            return ans > budget

        return bisect_left(range(n + 1), True, key=lambda a: f(a + 1))


s = Solution()
print(
    s.maximumRobots(
        chargeTimes=[3, 6, 1, 3, 4], runningCosts=[2, 1, 3, 4, 5], budget=25
    )
)


print(s.maximumRobots(chargeTimes=[11, 12, 19], runningCosts=[10, 8, 7], budget=19))


# a = list(range(0, 20, 2))
# print(a)
# print(bisect_left(a, 5))
